package graph.dfs;
import java.util.*;

/*
* 本题与lc797相同但是为acm模式
*
* 【题目描述】
给定一个有 n 个节点的有向无环图，节点编号从 1 到 n。请编写一个函数，找出并返回所有从节点 1 到节点 n 的路径。每条路径应以节点编号的列表形式表示。
【输入描述】
第一行包含两个整数 N，M，表示图中拥有 N 个节点，M 条边
后续 M 行，每行包含两个整数 s 和 t，表示图中的 s 节点与 t 节点中有一条路径
【输出描述】
输出所有的可达路径，路径中所有节点的后面跟一个空格，每条路径独占一行，存在多条路径，路径输出的顺序可任意。
如果不存在任何一条路径，则输出 -1。
*
*
*
5 5
1 3
3 5
1 2
2 4
4 5
*
1 3 5
1 2 4 5
* */
public class kama98_matrix {
    //邻接矩阵写法
    static List<List<Integer>> result = new ArrayList<>(); // 收集符合条件的路径
    static List<Integer> path = new ArrayList<>(); // 1节点到终点的路径

    public static void main(String[] args){
         Scanner scanner=new Scanner(System.in);
         int n= scanner.nextInt();
         int m= scanner.nextInt();
         int[][] graph=new int[n+1][n+1];
        for (int i = 0; i <m ; i++) {
            int s= scanner.nextInt();
            int t= scanner.nextInt();
            graph[s][t]=1;

        }
        path.add(1); // 无论什么路径已经是从1节点出发
        dfs(graph, 1, n); // 开始遍历

        // 输出结果
        if (result.isEmpty()) System.out.println(-1);
        for (List<Integer> pa : result) {
            for (int i = 0; i < pa.size() - 1; i++) {
                System.out.print(pa.get(i) + " ");
            }
            System.out.println(pa.get(pa.size() - 1));
        }

    }

    public static void dfs(int[][] graph, int x, int n){
        //当前遍历的节点到达了n 递归结束
        if(x==n){
            result.add(new ArrayList<>(path));
            return;
        }

        for (int i = 0; i <n ; i++) {// 遍历节点x链接的所有节点
            if(graph[x][i]==1){// 找到 x链接的节点
                path.add(i);// 遍历到的节点加入到路径中来
                dfs(graph,i,n);
                path.remove(path.size()-1);// 回溯，撤销本节点
            }
        }
    }
}
